public class DiameterOfBinaryTree {
    // leetcode 二叉树的直径
    // https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked
    /**
     * 通过观察可以发现，
     * 以某个节点为根节点的最长路径=左子树中到左子树根节点的最长路径的节点数+右子树中到右子树根节点的最长路径的节点数+2-1
     * 并且最终的结果可能经过根节点也可能不经过，所以我们需要对每个节点的情况都做出统计
     */
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        dfs(root);
        return ans - 1;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        ans = Math.max(ans, left + right + 1);
        return Math.max(left, right) + 1;
    }
}
